La catedral de Santa Eulàlia i Santa Júlia té els seus orígens en el moment de la creació del bisbat d'Elna en el segle VI. El temple actual és un dels quatre que formava el conjunt catedralici.

La més antiga de totes i que molt probablement era l'antiga catedral, estava dedicada a Sant Pere i es trobava en la part de la ciutat coneguda com Vila Baixa. Les darreres notícies que ens han arribat d'ella daten del 934. Ja en la Vila Alta es trobava l'església dedicada a Santa Maria del Bell-lloc. En una butlla papal del 897, es recorda que aquest temple va ser construït per Anastàsia, a la que tothom relaciona amb la germana de l'emperador Constantí I i tieta de Constantí II, assassinat a Elna l'any 350. A finals del segle XX es van destruir els vestigis que encara es conservaven d'aquest temple, tot i que corresponien a la reconstrucció feta en el segle XIII. L'altre temple, dedicat a Sant Esteve, sembla que es trobava a pocs metres a llevant de la capçalera de l'actual catedral.

L'església actual, s'esmenta per primera vegada l'any 861. En 922 es designada com la mare de totes les esglésies del Rosselló i el Conflent. Fou reconstruïda en el segle IX i consagrada de nou el 1 de setembre del 916 pel bisbe Elmerad.

A principis del segle XI es reconstrueix el temple, que consagrarà el bisbe Ramon d'Empúries l'any 1069.

Al voltant de l'any 1140, es fortifica la catedral i es construeixen uns valls per protegir les muralles de la ciutat per ordre del bisbe Udalgar de Castellnou.

Entre els anys 1380 i 1400 es comença a construir una nova capçalera gòtica per darrera de la romànica. Quan s'havien aixecat els murs de les capelles radials uns tres metres, es van aturar les obres. En 1674 es va intentar continuar l'obra sense èxit.

L'església té planta basilical, amb tres naus, capçades a l'est per tres absis semicirculars.

La nau central està coberta amb una volta de canó, mentre que les laterals presenten volta de quart de cercle. En tots dos casos van ser realitzades posteriorment, ja que en la construcció inicial es van utilitzar cobertes de fusta.

Als peus del temple, just per damunt de l'orgue, podem observar l'únic arc de diafragma que s'ha conservat, així com el lloc on anaven recolzades les bigues de fusta.

La separació entre les naus es realitza a través d'arcs formers de mig punt. Sorprèn la diferent estructura dels pilars en que es recolzen aquests arcs i que també serveixen de suport als arcs torals de totes les naus.

Els quatre pilars situats més a llevant són de planta cruciforme, amb semicolumnes adossades en els quatre costats, mentre que en la resta trobem pilastres rectangulars.

El segon pilar del costat nord presenta una característica diferent a la resta: la seva secció inferior té una estructura amb més ressalts que no pas en el tram superior. La unió entre tots dos espais es fa mitjançant una matussera motllura.

Les semicolumnes adossades presenten capitells esculpits bàsicament amb amb temàtica vegetal i geomètrica. Tot sembla indicar que, a excepció dels de la nau central, van ser reaprofitats d'una construcció anterior.

En substituir la coberta de fusta per voltes de pedra es van haver de reforçar els murs laterals de la nau principal. Aquesta acció va consistir en col·locar un tercer arc per damunt dels arcs formers, a mode d'arquivolta exterior.

L'absis principal està decorat externament amb uns grans arcs cecs de tradició alt-medieval.

Una imposta escacada recorre tot el cilindre absidal, creant una mena de timpà en cadascun dels arcs. Aquest està decorat amb quadrats col·locats en angle, recordant l'opus reticulatum, molt utilitzat en època romana i carolíngia.

Aquest absis va ser sobrealçat, probablement en el segle XII i per aquest motiu es van haver de construir dos grans arcbotants.

Des de l'exterior de l'absis principal, es pot endevinar l'existència d'una cripta, probablement eliminada en el moment de construir el monumental baldaquí del presbiteri l'any 1724. Precisament l'elevat pes d'aquest element fa inviable qualsevol excavació arqueològica en aquest sector. La cripta ocupava la totalitat de l'absis i probablement estava coberta per voltes d'aresta. En ella es veneraven les relíquies de Santa Eulàlia i santa Júlia, fins que en 1340 foren traslladades al darrera de l'altar.

Els absis laterals són molt més simples, decorats únicament amb lesenes, que no arriben fins a la cornisa.

A partir del segle XIII es van afegir capelles laterals en el mur sud. També es va construir una porta de marbre blanc en el segle XIV, reformada en 1669.

En la façana de ponent trobem la porta principal. Va ser construïda en el segle XIII i sorprèn per la seva simplicitat. Està formada per dos arcs de mig punt adovellats i en gradació, que envolta un timpà i llinda llisos. 

Com tot el temple, la façana està feta amb còdols disposats de manera irregular, tot i que en alguns sectors, com per exemple la part baixa, estan disposats en opus spicatum.

Per sobre del nivell de la porta trobem una decoració a base d'arcs llombards i lesenes. Els arcs, disposats en tres grups de dos a cada banda de la façana, estan resseguits per un arc fet amb basalt negre.

Aquesta decoració es repeteix en la base de les dues torres que flanquegen aquesta façana.

La torre del costat sud és contemporània del temple. Els primers nivells van ser edificats a finals del segle XI i presenten la decoració llombarda descrita anteriorment a base d'arcs cecs, resseguits amb basalt negre i lesenes. En els tres pisos superiors l'aparell dels arcs és molt més elaborat, amb carreus ben tallats, fet que els fa datar en ple segle XII. En els dos darrers pisos es van obrir dues finestres de mig punt en cada cara, corresponent-se amb els arcs centrals.

L'original façana romànica estava coronada amb un fris d'arcs cecs, que resseguien el pendent de la coberta a dues aigües. Aquesta decoració va ser parcialment destruïda en fortificar el temple i actualment només es conserven dos fragments.

Aquests arcs, com els altres de la façana, estaven decorats amb un arc de basalt negre, però el que els fa més interessant són les mènsules en que descansen els arcs. En les que s'han conservat podem veure motius geomètrics, vegetals i un cap humà.

La façana va ser concebuda amb dos campanars flanquejant-la, però només es va construir el del costat sud. En el segle XIV, per reforçar el sistema defensiu de la catedral, es decideix construir una altra torre en el costat nord, molt més petita, feta a base de còdols i maons.

En l'interior del temple es conserva l'ara d'altar consagrada l'any 1069. Per la part superior, que malauradament no pot veure el visitant, està decorada amb 30 arcs cecs i una elegant bordura amb perles i florons de tres pètals. En el segle XVIII es va convertir en frontal del nou altar i s'hi va gravar una inscripció relativa a la seva consagració.

Uns altres elements interessants són les dues piques de marbre que es conserven. Una és beneitera i té una estructura cilíndrica, decorada amb una fulla d'acant. És una peça romana del segle I, a la que se li van esculpir gallons i una acanalat interior per convertir-la en pica beneitera. L'altre pica és baptismal i no té cap decoració. Està datada entre els segles XII i XIII.

També es conserven nombrosos elements litúrgics i ornamentals de diferents èpoques. Entre ells podem trobar una Mare de Déu romànica i una gòtica, així com retaules gòtics i arquetes.

El claustre està adossat al costat nord del temple. No es conserven notícies de l'existència o la construcció del claustre fins l'any 1237. Prèviament, en època del bisbe Guillem Jordà (1171-86), es va substituir l'antic porxo de fusta, adossat al temple, per una galeria feta amb marbre. Entre 1237 i 1240 es recullen almoines per a construir les galeries oest i nord. Ja en el primer terç del segle XIV es completarà el claustre amb la construcció de la galeria est i la restauració de les altres galeries, molt malmeses per les tropes de Felip l'Ardit en 1285.  Al llarg del segle XIV es construeix un pis superior, que fou destruït l'any 1827, durant la restauració de la catedral.